#include <bits/stdc++.h>
using namespace std;

/*
611. 有效三角形的个数
已解答
中等
相关标签
premium lock icon
相关企业
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

 

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:

输入: nums = [4,2,3,4]
输出: 4
 

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
*/

// 法一
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 不足三条边
        int n = nums.size();
        if (n < 3)  return 0;

        sort(nums.begin(), nums.end()); // 排序
        int cnt = 0;

        // 找最大边
        for (int i = n - 1; i >= 2; --i) {      // 因为前面sort过
            int c = nums[i];
            // double pointer
            int left = 0, right = i - 1;

            // [0, i - 1] 满足a + b > c
            while (left < right) {
                int a = nums[left], b = nums[right];
                if (a + b > c) {
                    // 满足一个就cnt++  窗口滑动 范围变化
                    cnt+=right - left;
                    right--;
                } else      left++;
            }
        }
        return cnt;
    }
};